package com.sicheng.蓝桥.省赛.第九届;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/2/24 21:04
 */
public class 乘积最大 {
    /**
     * 给定N个整数A1, A2, ... AN。请你从中选出K个数，使其乘积最大。
     * <p>
     * 　　请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
     * <p>
     * 　　注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
     * 　　即：0-((0-x) % 1000000009)
     * 输入格式
     * 　　第一行包含两个整数N和K。
     * 　　以下N行每行一个整数Ai。
     * <p>
     * 　　对于40%的数据，1 <= K <= N <= 100
     * 　　对于60%的数据，1 <= K <= 1000
     * 　　对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
     * 输出格式
     * 　　一个整数，表示答案。
     * <p>
     * 样例输入
     * 5 3
     * -100000
     * -10000
     * 2
     * 100000
     * 10000
     * 样例输出
     * 999100009
     * <p>
     * 再例如：
     * 样例输入
     * 5 3
     * -100000
     * -100000
     * -2
     * -100000
     * -100000
     * 样例输出
     * -999999829
     */

    public static void main(String[] args) {

        // 读入 n ,k
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] nums = new int[n];
        // 依次读取数组元素,并给数组赋值
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 升序排序
        Arrays.sort(nums);
        int res = 1;
        //首元素 大于0, 则整个数组>0
        if (nums[0] >= 0) {
            // 最后k个元素相乘得到结果，因为他们是最大的
            for (int i = nums.length - 1; k >= 0; k--, i--) {
                res *= nums[i];
            }
            System.out.println(res);
            return;
        }


        //进入此处,说明首元素<0
        int[] dp = new int[2];
        dp[0] = nums[0];  //状态0,保存最小负数
        dp[1] = 1;        //状态1,保存最大正数
        for (int i = 1; i < nums.length; i++) {

            int dp0 = dp[0];

            if (nums[i] < 0) {
                dp[0] = Math.min(dp[0], dp[1] * nums[i]);// mim{ dp[0] ,最大正数 * nums[i] }
                dp[1] = Math.max(dp[1], dp0 * nums[i]);  // max{ dp[1] ,最小负数 * nums[i] }
            } else if (nums[i] > 0) {
                dp[0] = dp[0] * nums[i];
                dp[1] = dp[1] * nums[i];
            }
        }

        System.out.println(dp[1]);


    }
}
